package com.eloancn.leecode.solid_aim_offer.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 *  
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution34 {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root,sum);
        return res;
    }

    private void recur(TreeNode root, int sum) {
        if (root == null){
            return ;
        }
        path.add(root.val);
        sum -=root.val;
        if (sum ==0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left,sum);
        recur(root.right,sum);
        path.removeLast();

    }

    /**
     *  二叉树的先序遍历 通过递归方式来实现
     * @return
     */
    public List<Integer> preOrder(TreeNode headNode){
        List<Integer> res = new ArrayList<>();
        inorderTravel(res,headNode);
        return res;
    }
    private void inorderTravel(List<Integer> res,TreeNode cur){
        res.add(cur.val);
        if (cur.left !=null) {
            inorderTravel(res,cur.left);
        }
        if (cur.right!=null) {
            inorderTravel(res,cur.right);
        }

    }

    @Test
    public void runTest(){
        TreeNode headNode = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        headNode.left = node1;
        headNode.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        List<Integer> integers = preOrder(headNode);
        System.out.println(integers);

    }
}
